package com.msb.class04;

/**
 * @Auther: jiudianliu
 * @Date: 2024/3/3 - 03 - 03 - 16:40
 * @Description: com.msb.class04
 * @version: 1.0    单双链表 翻转
 */
public class LinkedList {

    //单链表 节点
    public static class Node {
        public int value ;
        public Node next ;
        public Node(int data){
            value = data ;
        }
    }

    //

    // 双链表  节点
    public static class DoubleNode {
        public int value ;
        public DoubleNode last ;
        public DoubleNode next ;
        public DoubleNode(int data) {
             value = data ;
         }
    }


    // 实现单链表 反转  传入的head 其实是上边的n1另一个复制地址，上层n1不变
    public static Node reverseLinkedList(Node head){
        //  让反转前的头结点指向空，然后依次指向前一个节点  pre始终是head的前一个节点的位置
        Node pre = null ;
        // 记录下一个节点的位置
        Node next = null ;
        //
        while( head != null){
            // 此时 将next 指向 head.next的位置  记录下一个节点位置
            next = head.next ;
            // 然后 将 head.next 指向 pre
            head.next = pre ;
            // 然后 将 pre 指向 head
            pre = head ;
            // 然后 将head来到下一个head的下一个位置
            head = next ;
        }
        return  pre ;
    }

    // 双链表 反转
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null ;
        DoubleNode next = null ;
        while ( head != null){
            // next 记住head的下一个位置
            next = head.next ;
            // 然后把head的next指向pre null值
            head.next = pre ;
            // 然后把head.last指针指向next
            head.last = next ;
            // 然后pre指向head
            pre = head ;
            // head跳到next的位置
            head = next ;
        }
        return pre ;
    }
    public static void main(String[] args) {
        // 创建单链表  1 2 3
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);

        DoubleNode d1 = new DoubleNode(1 ) ;
        DoubleNode d2 = new DoubleNode(2 ) ;
        DoubleNode d3 = new DoubleNode(3 ) ;
        DoubleNode d4 = new DoubleNode(4 ) ;
        DoubleNode d5 = new DoubleNode(5 ) ;
        d1.next = d2 ;
        d2.next = d3 ;
        d2.last = d1 ;
        d3.next = d4 ;
        d3.last = d2 ;
        d4.next = d5 ;
        d4.last = d3 ;

        DoubleNode doubleNode = reverseDoubleList(d1);

        while (doubleNode != null){
            System.out.print(doubleNode.value + " ");
            doubleNode = doubleNode.next ;
        }
        System.out.println();
    }


}
